package com.dycong.common.dataStructuresAndAlgorithms.sort;

/**
 * Created by dycong on 2016/12/3.
 */
public class BucketSort {


    /**
     * @see 桶形排序
     * 输入数据A1,A2,A3,A4..An必须只由小于Max的整数组成(显然还可以对其进行扩充).如果是这种情况;
     * 使用一个大小为Max+1的的bucket数组，他被初始化为全0，于是，bocket有Max+1个单元或桶。
     * 当Ai读入时，bucket[Ai]增一，在所有的输入数据读入后，扫描数组bucket,打印排序后的表。
     * @param a
     * @param Max
     */
    public static void bucketSort(int[] a, int Max) {
        long[] bucket = new long[Max + 1];
        for (int i = 0; i < bucket.length; i++)
            bucket[i] = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i]<0)
                throw new IllegalArgumentException("数组元素均应处于0与Max之间的整数");
            bucket[a[i]]++;
        }
        int j = 0;
        for (int i = 0; i < bucket.length; i++) {
            long k = bucket[i];
            for (; k > 0; k--)
                a[j++] = i;
        }
    }

    public static int test(int[] a,int l){
        int t=0;
        for (int i=0;i<a.length;i++){
            if (a[i]==l)
                t++;
        }
        return t;
    }

    public static void main(String[] args) {
        int k=35000000;
        Integer[] array = new java.util.Random().ints(0, 3500).limit(k).boxed().toArray(Integer[]::new);
        int[] arr=new int[k];
        for (int i=0;i<array.length;i++)
            arr[i]=array[i].intValue();
        int[] arr1=new int[k];
        for (int i=0;i<array.length;i++)
            arr1[i]=array[i].intValue();
        long t=System.currentTimeMillis();
        bucketSort(arr,3500);
        System.out.println(System.currentTimeMillis()-t);


       /* for (int i=0;i<arr.length-1;i++){
            if (arr[i]>arr[i+1])
                System.out.println(false);
            if (test(arr1,arr[i])==0)
                System.out.println(false);
        }*/
    }
}
